In a broadband telecommunications network, a transport protocol is used to transfer information end-to-end over a wide variety of channels, matching the requirements of various applications to the network capabilities. One important aspect of the transport protocol is the problem of error control. When the communications network provides an unacceptable error rate, the transport protocol must detect the errors and recover lost information. Ideally, the transport protocol provides a channel with acceptable reliability, without violating an application's requirements for throughput, delay or cost.
Several coding techniques are presently utilized to improve the reliability of a channel. In an Automatic Repeat request (ARQ) system, enough parity bits are transmitted to detect an error using an error detection code (see, e.g., P. G. Farrell, "Influence of LSI and VLSI Technology on the Design of Error Correction Coding Systems," Proc. IEE, Vol. 129, Pt.F, No. 5, October 1982). However, corrupted data must always be retransmitted since there is not enough information in the parity bits to correct the detected errors. The number of retransmissions depends on the channel error distribution so there is no guarantee that there will be an upper bound on the delay.
In a Forward Error Correction (FEC) code, enough extra parity bits are transmitted to enable a receiver to correct the maximum expected amount of corrupted data without any further retransmission. (See, e.g., R. J. McEliece, "The Theory of Information and Coding," Addison Wesley, 1977; I-S. Hsu, I. Reed, T. Truong, K. Wang, C-S Yeh and L. Deutch, "The VLSI Implementation of a Reed-Solomon Encoder Using Berlekamp's Bit-Serial Multiplier Algorithm," IEEE Transactions on Computers, Vol. 33, No. 10, pp. 906-911, October 1984; H. Shoa, T. Truong, L. Deutch, J. Yuen and I. Reed, "A VLSI Design of a Reed-Solomon Decoder," IEEE Transactions on Computers, Vol. 33, No. 10, pp. 906-911, October 1984; H. Shoa and I. Reed, "On the VLSI Design of a Reed-Solomon Decoder Using Systolic Arrays, " IEEE Transactions on Computers, Vol. 37, No. 10, pp. 1273-1280, October 1988). An FEC Code is used when a return channel is unavailable or too slow. Typically, an FEC code is utilized in satellite or deep space telecommunications.
There are also hybrid schemes which combine some features of both ARQ and FEC codes. In one hybrid scheme, the receiver uses the transmitted parity bits for error correction and error detection. The receiver corrects a certain number of errors using an error correction code (like FEC), but when there are two many errors, the receiver uses an error detection code to request retransmission (like ARQ). In an alternative hybrid scheme, the original message is generated just like in a pure ARQ scheme, with only enough extra bits transmitted to allow the receiver to perform error detection. However, when a retransmission is requested, the transmitter sends parity bits from an FEC code so that the receiver can reconstruct the lost data, rather than retransmitting the entire message.
In present day commercial telecommunications and computer systems, ARQ is used almost exclusively. In particular, because telephone channels have variable capacity, FEC is inefficient or unreliable. In addition, because of the complexity of available FEC algorithms, FEC is too slow or expensive.
However, ARQ correction codes are generally not suitable for use in broadband networks. More specifically, some real-time applications such as video transmissions require a guaranteed end-to-end delay; typically the response time of a human--say 50 ms to 500 ms. For a 5000 kilometer transcontinental link, with a one-way communication delay of approximately 25 ms to 50 ms, simple ARQ cannot be utilized because the number of retransmissions required will cause delays to be outside the acceptable range.
A further difficulty in using ARQ in broadband networks is that the hardware required for ARQ grows rapidly as the bandwidth increases.
An additional problem with ARQ in broadband networks relates to the multicasting application. In a multicasting application, data is transmitted from a source to a selected plurality of receivers. Because of the large number of receivers in a multicast system, ARQ degrades significantly. Latency is large even for low error rates because the number of retransmissions is determined by the number of receivers. Transmitter complexity is also proportional to the number of receivers as a block of transmitted data cannot be deleted from the transmitter until an acknowledgement (negative or positive) is received from the entire multicast group.
For broadband networks, FEC is more efficient than ARQ. FEC encoding and decoding delays can be kept small compared to the communications time. Specifically, FEC has a maximum latency of only a one-way communication. In addition, in contrast to ARQ, FEC always makes an attempt to decode and correct errors, thereby reducing the need to store and manage transmitted data at the source. Therefore in comparison to ARQ, FEC is preferable for wideband multicasting applications. In addition, FEC hardware may be less complex than ARQ hardware at high bit rates.
Presently available high performance, low latency FEC codes are computationally demanding. For example, the Reed-Solomon (RS) cyclic word error correction code has only recently been implemented on a single VLSI chip that can run at rates on the order of 100 megabits per second.
Other FEC codes (see, e.g., M. O. Rabin, "Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance," Journal of the ACM, Vol. 36, No. 2, pp. 335-348, April 1989) suffer from various drawbacks, including that the original data is not transmitted in clear form and that the codes are computationally complex so that they are slow and also difficult to implement.
In view of the foregoing, it is an object of the present invention to provide an FEC code which is computationally simpler than existing FEC codes. It is a further object of the invention to provide a simplified version of an RS code suitable for use in a broadband network.
In a conventional telecommunications network, link error characteristics are strongly influenced by impulse noise (e.e., lightning near copper telephone wires) so that errors occur at random times and in bursts of random duration. In broadband networks, fiber optic transmission facilities are utilized so that this type of error does not predominate. Instead, in a broadband network, the predominant error results from congestion at the network switches. In a broadband network, data is organized into cells and routed from a source through a sequence of switches to a destination. If a switch cannot route or buffer a cell, the cell is lost. Thus, errors which occur in broadband networks are in the form of burst erasures of one or more cells. This property enables a substantial simplification of FEC codes used in broadband network because the data may be transmitted in such a way that the locations of the errors are known.
In coding theory, an error is defined as a corrupted bit or symbol with an unknown value in an unknown location An erasure is defined as corrupted bit or symbol with an unknown value but with a known location. As indicated above, losses due to switch congestion in a broadband network fall into the erasure category.
Accordingly, it is an additional object of the present invention to provide a very simple FEC code which can correct erasures in transmitted data. It is a still further object of the invention to provide an FEC code which can be utilized for erasure correction in a broadband network.